/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:何人亮
 * Date:2024-07-27
 * 20:59
 */
public class QuickSort {
    public static void quickSort(int[] array){
        quick2(array,0,array.length-1);
        // write code  here
    }

    private static void quick(int[] array, int start, int end) {
        if(start>=end){
            return ;
        }
        int pivot = partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    private static int partition(int[] array,int stact,int end){
        int tem=array[stact];
        int left=stact;
        int right=end;
        while (left<right){
            while (left<right&&array[right]>=tem){
                right--;
            }
            array[left]=array[right];
            while (left<right&&array[left]<=tem){
                left++;
            }
            array[right]=array[left];
        }
        array[right]=tem;
        return right;
    }
    private static void quick2(int[] array, int start, int end) {//优化后的
        if(start>=end){
            return ;
        }
        int midIndex=midIndex(array,start,end);//三数取中法
        swap(array,start,midIndex);
        int pivot = partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }

    private static int midIndex(int[] array, int start, int end) {
        int mid=(start+end)/2;
        if(array[start]<array[end]){
            if(array[mid]<array[start]){
                return start;
            } else if (array[mid]>array[end]) {
                return end;
            } else  {
                return mid;
            }
        }else {
            if(array[mid]<array[end]){
                return end;
            } else if (array[mid]>array[start]) {
                return start;
            } else  {
                return mid;
            }
        }
    }

    private static void swap(int[] array,int i,int j) {
        int tem = array[i];
        array[i] = array[j];
        array[i] = tem;
    }
}
